\documentclass[compressed,narroweqnarray,inline]{ieee}
%\documentclass[%
%	%draft,
%	%submission,
%	%compressed,
%	final,
%	%
%	%technote,
%	%internal,
%	%submitted,
%	%inpress,
%	reprint,
%	%
%	%titlepage,
%	notitlepage,
%	%anonymous,
%	narroweqnarray,
%	inline
%	%twoside
%	]{ieee}

\usepackage{ieeefig}
\usepackage{listings}
\usepackage{pdfcolmk}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage{verbatim}
\usepackage{wrapfig}
\usepackage{moreverb}
\usepackage{fancyhdr}
\usepackage{xcolor}
\usepackage{color}
\usepackage{url}

\linespread{1.3} % 1.5 line spacing
\begin{document}

%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[A Basic Technical Overview of Common Lisp]{%
       An Overview of Scoping, Syntax, Operators and Data Types in the Common Lisp Programming Language}

% format author this way for journal articles.
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Student Member}
      \authorinfo{%
      A. Computer Science Undergraduate Student,
      University of Maine, Orono ME 04469, USA,
      Phone: \mbox{(347) 210-0185}, email: \mbox{anthony.naddeo@gmail.com}}
  }

% format author this way for conference proceedings
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Fellow}
      \authorinfo{%
      Computer Science Undergraduate Student\\
      University of Maine, Orono ME 04469, USA\\
      Phone: (347) 210-0185, email: anthony.naddeo@gmail.com}
  }

% specifiy the journal name
\journal{COS 301, 2011}

% Or, specify the conference place and date.
%\confplacedate{Ottawa, Canada, May 19--21, 1997}

% make the title
\maketitle        

\newpage
\begin{abstract}  
In this paper, we will examine some of the general technical aspects of the Common Lisp programming language, particularly relating to syntax, operators, scoping and typing. This paper is not a comprehensive replacement for the Common Lisp specification. However, it does offer direct, concrete examples to clarify the reasoning behind behavior in the specification and some noteworthy implementations. 
\end{abstract}

% do the keywords
\begin{keywords}
Lisp, programming language, syntax, scoping, operators, types, Common Lisp
\end{keywords}

%config the listings settings
\lstset{language=Lisp,
identifierstyle=\ttfamily,
breaklines=true,
tabsize=2,
%title=\lstname,
basicstyle=\footnotesize,
keywordstyle=\color[rgb]{0,0.5,0},
commentstyle=\color{gray},
stringstyle=\color{red}}

\tableofcontents
\newpage
 
%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section{Introduction}\label{sec:intro}
\PARstart Understanding the syntax, scoping principles, operator meanings and data types are central to understaning a language itself, especially if that language happens to be Common Lisp.

This paper avoids trying to condense the Common Lisp specification into ten pages. Instead, representative examples of core concepts are chosen and explained along side the more common data types (there are far too many to possibly comprehensively explain in this paper). 

%----------------------------------------------------------------------
% SECTION II: Syntax
%----------------------------------------------------------------------
\section{Syntax}\label{sec:syntax}
Lisp understandably appears foreign to many programmers coming from a curly-brace background. An easy way to understand the syntax for these programmers is to compare Lisp source code with a more common language like C. The following snippets are the C and Lisp version of the Hello World program.

\begin{figure}[H]
\lstinputlisting[language=C]{data/hello.c}
\caption{hello.c}
\label{fig:hello.c}
\end{figure}

\begin{figure}[H]
\lstinputlisting{data/hello.lsp}
\caption{hello.lsp}
\label{fig:hello.lsp}
\end{figure}

In Lisp, parenthesis form lists, which are composed of parts called atoms, and all whitespace is ignored. The first atom of a list is also a function or a macro that gets applied to the rest of the atoms \cite {successful_lisp_syntax}. In \texttt{hello.lsp} the \texttt{defun} macro is used to define the function \texttt{main}. Inside of \texttt{main} the \texttt{format} function is used to print a string to the terminal, which is specified by the \texttt{t} argument. \texttt{format} behaves much like \texttt{printf}, though it was apparently inspired by Fortran's \texttt{format} function\cite{successful_lisp_format}. hello.lsp defines a main method, but that is optional. It could have just as easily been \texttt{(format t ``Hello World'')}. 

A list can be defined in the same fashion as the application itself (which is a list to the Lisp interpreter). Creating a list and setting it to a variable would look like the following.

\begin{lstlisting}
(set `var `(1 2 3 (``fish'' ``dogs'') 4))
\end{lstlisting}

Here a two dimentional list is created and assigned to a variable \texttt{var}. The apostrophe that appears before the variable name and the list tells Lisp that these lists should not be evaluated. If they were absent then \texttt{var} is assumed to be an existing variable and the number 1 is assumed to be the name of a function, with the rest of the list being arguments. The apostrophe was required so often that Common Lisp included a \texttt{setq} function that automatically quotes the first argument\cite{successful_lisp_macros}.

\begin{lstlisting}
(setq var `(1 2 3 (``fish'' ``dogs'') 4))
\end{lstlisting}

Everything in Lisp follows this simple, elegant syntax. At more complex levels the parenthesis can seem overwhelming but most IDEs will help with matching and closing pairs of parenthesis.


%----------------------------------------------------------------------
% SECTION III: Operators
%----------------------------------------------------------------------
\section{Operators}\label{sec:operators}
The concept of operators in Common Lisp is not exactly straight forward. The syntax of the language makes it difficult to draw a direct parallel with expressions in languages such as C that represent more what humans tend to write in practice. For example, the expression \verb|5 + 5| in C will return 10. In Lisp, this is written as \verb|(+ 5 5)| where \texttt{+} is no different than any other function name. The following code demonstrates this ambiguity.

\begin{lstlisting}
(defun ++ (x)
  (+ x 1))

(print (+ 5 5))
==> 10

(print (++ 5))
==> 6
\end{lstlisting}

The \texttt{++} operator does not exist in the Common Lisp standard as it does in C, yet we can implement it ourselves as a simple function and call it the same way we would with addition. Any language could define a new method to implement missing functinality in some way, and some languages can even overload operators to change their meanings in certain contexts. The problem with Common Lisp then is that function calls and operators are used exactly the same way with little restriction on the use of symbols in the names of their functions. That being said, the Common Lisp specificatino does explicitly mention three boolean operators \texttt{and}, \texttt{or}, and \texttt{not}\cite{common_lisp_operator}. The following is a quote by Steele in his Common Lisp specification\cite{common_lisp_predicate}.\\

\textit{``If neither equal nor equalp is found to be appropriate in a particular situation, programmers are encouraged to create another operator that is appropriate rather than blame equal or equalp for ``doing the wrong thing.''}\\

The method a programmer would use to ``create'' his own operator would be the same method used to create a function, \texttt{defun} or \texttt{defmethod}, thus blurring the distinction between operators and functions. This is just another example of a powerful, flexible feature that feels right at home in Common Lisp.

%----------------------------------------------------------------------
% SECTION IV: Scoping
%----------------------------------------------------------------------
\section{Scoping}\label{sec:scoping}
Guy Steele specified four scoping properties in his Common Lisp specification\cite{common_lisp_scope}.

\begin{itemize}
\item \textbf{Lexical Scope.} This is what most C developers are used to. A reference to a variable is contained to a portion of the code, such as a function body.
\item \textbf{Indefinite Scope}. References to variables may appear anywhere in any program. 
\item \textbf{Dynamic Context}. This is most accurately described to non-lisp persons as a dynamically scoped variable, though it is technically a single charactetistic of those varibales and not the sole embodiment.
\item \textbf{Indefinite Context}. Most Common Lisp objects have indefinite context and can be referenced as long as the object has not been destroyed and reference to that object has not been lost. 
\end{itemize} 

Steele considers the term \textit{dynamic scoping} a misnomer and defines it as the combination of indefinite scope and dynamnic context.

The scope of a Common Lisp variable is largely depedent on the context in which it was created. A variable can be dynamically typed or lexically typed at the discretion of a programmer.

%----------------------------------------------------------------------
\subsection{Lexical Variables}\label{sec:static}
Scoping in Common Lisp is lexical by default, and dynamic when declared so. With this flexibility, variable scoping can become quite confusing. The best way to explain which scoping is in effect is through a series of code snippets, starting with the most simple, lexical example.

\begin{figure}[H]
\begin{lstlisting}
(defmethod fun1 (x)
  (print x))

(fun1 5) 
==> 5
\end{lstlisting}
\caption{}
\label{fig:simple_lexical}
\end{figure}

The variable \texttt{x} is an example of a variable with lexical scope. It is accessible only from within the body of the \texttt{fun1} function and nowhere else. To verify this, we can alter the above source code to try and access \texttt{x} from outside of the function body.

\begin{figure}[H]
\begin{lstlisting}
(defmethod fun1 (x)
  (print x)
  (fun2))

(defmethod fun2 ()
  (print x))

(fun1 5)
==> 5
*** - EVAL: variable X has no value
\end{lstlisting}
\caption{}
\label{fig:simple_lexical2}
\end{figure}

The program crashes when \texttt{fun2} is called because the variable \texttt{x} is not in its scope and is therefore undefined. Furthermore, even if \texttt{x} has been passed to \texttt{fun2} as a parameter, it would not reference the same lexically scoped \texttt{x} that resides in \texttt{fun1}. 


\begin{figure}[H]
\begin{lstlisting}
(defmethod fun1 (x)
  (print x)
  (fun2 x)
  (print x))

(defmethod fun2 (x)
  (setf x 10)
  (print x))

(fun1 5)
==> 5
==> 10
==> 5
\end{lstlisting}
\caption{}
\label{fig:simple_lexical3}
\end{figure}

The call to \texttt{setf} in \texttt{fun2} is assigning a value to its own variable \texttt{x} and does not effect the value of the variable in \texttt{fun1}. The introduction of dynamic variables would change these circumstances.

%Going back to Figure \ref{fig:simple_lexical2}, the following modification can be made to demonstrate the behavior when dynamic variables are introduced.

%----------------------------------------------------------------------
\subsection{Dynamic Variables}\label{sec:dynamic}
Dynamic variables (or ``special'' variables as they are referred to in Lisp) are accesible anywhere in a program, so long as there are no lexical variables shadowing them.


\begin{figure}[H]
\begin{lstlisting}
(defvar x 100)
(defun fun1 ()
  (print x)

(defun fun2 (x)
  (print x))

(fun1)
==> 100

(fun2 5)
==> 5
\end{lstlisting}
\caption{}
\label{fig:simple_dynamic}
\end{figure}

The value of \texttt{x} in \texttt{fun1} is known despite not having it explicitly passed, while a local binding of \texttt{x} takes precedence in \texttt{fun2}. This is because \texttt{x} was declared dynamic by the function \texttt{defvar}. 

Dynamic scoping can lead to some confusing behavior if programmers are not conscious of it. Adding a dynamic variable declaration to figure \ref{fig:simple_lexical2} demonstrates this.

\begin{figure}[H]
\begin{lstlisting}
(defvar x 100)

(defmethod fun1 (x)
  (print x)
  (fun2))

(defmethod fun2 ()
  (print x))

(fun1 5)
==> 5
5
\end{lstlisting}
\caption{}
\label{fig:dynamic_lexical2}
\end{figure}

Previously, this program crashed when it reached \texttt{fun2} because \texttt{x} was not defined. Now that \texttt{x} is dynamic (thanks to \texttt{defvar}), \textit{all} instances of the variable \texttt{x} are considered dynamic, even the if they appear as function parameters like they do in \texttt{fun1}. \texttt{fun2} is now allowed to treat \texttt{x} as dynamic and starts searching the call stack for bindings. The first one it sees is in \texttt{fun1} so it takes on a value of 5. For this reason it became important to distinguish between dynamic and lexical variables. By convention, a dynamically scoped variable would have its name surrounded with ``*'' to avoid confusion\cite{cl_api_defvar}.

This is particularly confusing becuase similar code in other languages yield different results. For exmample, here is figure \ref{fig:dynamic_lexical2} translated into C.

\begin{figure}[H]
\begin{lstlisting}
int x = 100;

void fun2(){
  printf("Second: %i\n",x);
}

void fun1(int x){
  printf("First: %i\n",x);
  fun2();
}

void main(){
  fun1(5);
}

==> 5
100
\end{lstlisting}
\caption{}
\label{fig:dynamic_c}
\end{figure}

\texttt{fun2} returns 100 in C because there is strictly lexical scoping. \texttt{fun2} does not recurse the call stack to find a value of \texttt{x}, it just assumes it is a global variable and takes the value from there.

Interestingly enough, changing the \texttt{defvar} in figure \ref{fig:dynamic_lexical2} to \texttt{setf} causes \texttt{x} to behave more like a global variable in C.


\begin{figure}[H]
\begin{lstlisting}
(setf x 100)

(defmethod fun1 (x)
  (print x)
  (fun2))

(defmethod fun2 ()
  (print x))

(fun1 5)
==> 5
100
\end{lstlisting}
\caption{}
\label{fig:dynamic_lexical3}
\end{figure}

The problem here is that \texttt{setf} is defined in the Common Lisp specification as assigning a value to a variable, \textit{not} creating a variable itself\cite{cl_api_defvar}. The actual behavior is officially ``undefined'' when used in this context. The reasoning behind this is not very clear as it is implementation specific, but it is \textit{not} something that should be counted on. 

%----------------------------------------------------------------------
% SECTION V: Data Types 
%----------------------------------------------------------------------
\section{Data Types}\label{sec:types}
Common Lisp is rich in data types despite being a dynamically typed language. This section will give an overview of the more common data types.

%----------------------------------------------------------------------
\subsection{Numbers}\label{sec:numbers}
The \textit{number} data type is the parent of many differnt types of numbers such as \textit{integer}, \textit{ratio}, \textit{floating-point} and \textit{complex}.

%-----------------------------------
\subsubsection{Integers}\label{sec:integers}
The \textit{integer} data type in Common Lisp is not rigid specification so the actual size is largely implementation specific. The only restriction is a minimum size of $[-2^n, 2^n-1]$ where $n >= 15$, which is comparable to the \textit{short int} type in C\cite{common_lisp_integer}.

A series of variables were specefied in order to allow programmers to obtain the maximum and minimum sizes of various numbers in their chosen implementation. For integers, these variables are \textit{most-positive-fixnum} and \textit{most-negative-fixnum}. Here are some notable Common Lisp implementations and their respective integer fixnum sizes\cite{cl_api_fixnum}.

\begin{itemize}
\item \textbf{Clisp}: 281474976710655
\item \textbf{SBCL}: 1152921504606846975
\item \textbf{SLIME}: 1152921504606846975
\end{itemize}

Anything larger than these numbers will be considered \textit{bignum} types and takes a much room as they need to represent an integer. The exact representation is also implementation specific.

%can write numbers in any radix like this: #nrdddd. #2r=#b, #8r=#0, #x=#16r

%-----------------------------------
\subsubsection{Floats}\label{sec:float}
Like integers, a lot of the details of the \textit{float} type are left to the discression of the implementation. However, Common Lisp does specify four general categories for floating point types.

\begin{itemize}
\item \textbf{short-float}. Recommends a minimum precision of 13 bits and a minimum exponent size of 5 bits. This is the smallest float type available.
\item \textbf{long-float}. Recommends a minimum precision of 50 bits and a minimum exponent size of 8 bits. This is the longest float available.
\item \textbf{single-float}. Recommends a minimum precision of 24 bits and a minimum exponent size of 8 bits. This is a middle ground between the short and long types.
\item \textbf{double-float}. Recommends a minimum precision of 50 bits and a minimum exponent size of 8 bits.This is a middle ground between the single and long types.
\end{itemize}

The \textit{double-float} type is simultaneously described as being a middle ground type while having the same recommended values as a \textit{long-float}. The following are the max values that the Clisp implementation decided upon\cite{common_lisp_float}.

\begin{itemize}
\item \textbf{short-float}. 3.4028s38
\item \textbf{long-float}. 8.8080652584198167656L646456992
\item \textbf{single-float}. 3.4028235E38
\item \textbf{double-float}. 1.7976931348623157d308
\end{itemize}

Just as with integers, these values can be obtained by printing special variables defined in each specefication\cite{cl_api}.

%----------------------------------------------------------------------
\subsection{Characters}\label{sec:characters}


%----------------------------------------------------------------------
\subsection{Symbols}\label{sec:symbols}
The \textit{symbol} type is where Common Lisp (Lisp in general) starts to shine as a unique language. A \textit{symbol} is composed of three main components.

\begin{itemize}
\item \textbf{Property List}. This is a list of key-value pairs that belong to the symbol. Common Lisp has built in hash tables and lists that are easier to work so these are not used as often as they once were.
\item \textbf{Package Cell}. Refers to the \textit{package} object that owns the symbol. Packages were Common Lisps answer to name collisions in large scale applications, similar in concept to modern day Java packages. 
\item \textbf{Print Name}. This is the name associated with the symbol, analagous to a variable name, but represented as strings. This name is used to find a symbol in a particular package as well as reference a symbol directly. 
\end{itemize}

Each of these properties are free to be defined and redefined by the programmer just like any other variable. One very powerful an interesting feature of symbols in Common Lisp is the abliity to bind a symbol to a function and a value simultaneously. The following code demonstrates this. A value bound variable is referred to as bound, while a function bound variable is referred to as fbound.

\begin{figure}[H]
\begin{lstlisting}
; create a function
(defun fun (string)
  (print string)
  string)


(setf sym (make-symbol ``sym''))                      ; create a symbol sym
(setf (symbol-function `sym) (symbol-function `fun))  ; fbind sym
(setf sym 5)                                          ; bind sym

(sym (fun 20))
==> 20
20

(sym (fun sym))
==> 5
5

(print sym)
==> 5
\end{lstlisting}
\caption{}
\label{fig:symbols}
\end{figure}

The symbol \texttt{sym} is created from a string (print name), then it is fbound and bound. That symbol can then be used to call the \texttt{fun} function or to represent the value 5 depending on the context.

%----------------------------------------------------------------------
\subsection{Lists and Conses}\label{sec:lists}
Lists are the core data structure of Common Lisp. The easiest way to understand them is to think of them as singly linked lists composed of nodes where each node is called a conse. Like a node, a conse has a link to the next conse in the list, which is referred to as a \textit{cdr}. The first conse in a list is referred to as a \textit{car}. Common Lisp has functions named \texttt{cdr} and \texttt{cons} that return the next conse and first conse, respectively. 

\begin{figure}[H]
\begin{lstlisting}
(setf x `(1 2 3 4))
(print x)       ; the list
==> (1 2 3 4)

(print (car x)) ; the first element
==> 1

(print (cdr x)) ; the list that the first element points to
==> (2 3 4)
\end{lstlisting}
\caption{}
\label{fig:symbols}
\end{figure}

The \texttt{car} and \texttt{cdr} forms can be combined to create \texttt{cadr} which is the quivelant of calling \texttt{(car (cdr `(1 2 3 4)))}. The ``a'' and the ``d'' can also be repeated up to four times as a convenient method to express a long nested \texttt{car} or \texttt{cdr} expression. For example, \texttt{(cdr (cdr (cdr `(1 2 3 4))))} can be represented as \texttt{(cdddr `(1 2 3 4))}. 

Lists in Common Lisp are always \texttt{nil} terminated unless a dot notation is used. Representing a list as \texttt{(1 2 3 . 4)} would return a list with three elements in it, the third of which would have an integer \texttt{cdr} of 4, as opposed to \texttt{nil} or another conse. 


%----------------------------------------------------------------------
\subsection{Characters}\label{sec:char}
Common Lisp \textit{character} objects are simple and striaght forward. For most intents and purposes, they can be thought of the same way as in C and C++, but with different syntax. While in C, the character ``a'' is represented as \verb|\a|, Common Lisp represents it as \verb|\#a|. 

Common Lisp has support for the standrad ninety-five printing characters in ASCII, as well as a newline character represented as \verb|\#newline|.



%----------------------------------------------------------------------
% SECTION VI: Conclusion
%----------------------------------------------------------------------
\section{Conclusion}\label{sec:conclusion}
Superficially, it is possible to look at Common Lisp as just another programming language and code in it as though it were C or Java. It really does take a technical examination, like this paper, to realize the power and potential programmers hold when they are programming in Common Lisp. No other language (excluding other Lisp dialects) have such a flexible, laissez-faire approach to functions, operators and bindings, while simultaneously maintaining a concrete, simple and elegant syntax to solve problems with. In the words of Philip Greenspun\cite{philip_greenspun},\\

\textit{``Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.''}\\


\newpage
%----------------------------------------------------------------------
% SECTION X: APENDIX
%----------------------------------------------------------------------
\section{Apendix}\label{sec:apendix}
\subsection{Recursive Descent Parser iplemented in Common Lisp}

\begin{lstlisting}
(defvar *tokenString* `(``id'' ``&&'' ``(`` ``id'' ``||'' ``id'' ``)'' ))
(defvar *token* (car *tokenString*)) ;; current token

;; Token functions

;; Sets *token* to the next token in the
;; token string for this parse
(defmethod nextToken ()
  (setf *tokenString* (cdr *tokenString*))
  (setf *token* (car *tokenString*)))
 

;; Tests the current token against another and
;; if they are equal then set *token* to the
;; next token
(defmethod matchNext (token)
  (if (string= token *token*)
      (progn (nextToken) (format t ``found ~s~% stream: ~s~%~%'' token *tokenString*) 1)
      (format t ``~s does not match ~s~% steam: ~s~%~%'' token *token* *tokenString*)))

;; just like matchNext, but throws and error
;; if there is no match
(defmethod requireNext (token)
  (format t ``REQUIRE: ``)
  (if (matchNext token)
      1
    (error ``Unexpected token; not a sentence'')))


;; start
(defmethod bool_expr ()
  (format t ``_____________Starting bool_expr~%'')
  (and_term)
  (if (matchNext ``||'')
      (and_term))
  1)


(defmethod and_term ()
  (format t ``_____________Starting and_term~%'')
  (bool_factor)
  (if (matchNext ``&&'')
      (bool_factor)))
  
(defmethod bool_factor ()
  (format t ``_____________Starting bool_factor~%'')
  (if (matchNext ``(``)
      (progn (bool_expr) (requireNext ``)''))
      (if (matchNext ``!'') ;;elif
    (bool_factor)
    (if (or (matchNext ``true'') (matchNext ``false'')) ;;elif
        ()
        (relation_expr))))) ;;else

 
(defmethod relation_expr ()
  (format t ``_____________Starting relation_expr~%'')
  (requireNext ``id'')  
  (if (or (matchNext ``=='') (matchNext ``!='') (matchNext ``<'') (matchNext ``>'') (matchNext ``<='') (matchNext ``>='')  )
      (requireNext ``id'')))



(defun parse ()
  (bool_expr)
  (if (= (list-length *tokenString*) 0)
      (format t ``String is valid~%'')
    (format t ``Not a sentence~%'')))
\end{lstlisting}

%----------------------------------------------------------------------
% SECTION X: Bibliography
%----------------------------------------------------------------------

\newpage
\begin{thebibliography}{1}
\bibliographystyle{IEEEbib}
\bibliography{bibliography}
\end{thebibliography}

\end{document}









